package com.cong.sort.insertion;

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {11, 5, 8, 77, 66, 55, 32};
        print(arr);
        sort2(arr);
        System.out.println();
        print(arr);

    }

    /**
     * 排序方法
     *
     * @param arr
     */
    public static void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) swap(arr, j, j - 1);
            }
        }

    }


    /**
     * 排序方法
     *
     * @param arr
     */
    public static void sort2(int[] arr) {
        int temp = 0;
        //从i=1 开始，因为单独一个元素arr[0]是有序的；
        for (int i = 1; i < arr.length; i++) {
            //从无序列表中取值
            temp = arr[i];
            int t = i-1;
            //往前寻找，只到找到比temp小的值且数组下标不能越界为止，
            while (t>=0 && arr[t]>temp){
                //找到之后交换位置
                arr[t+1] = arr[t];
                t--;
            }
            //将temp
            arr[t+1]=temp;

        }

    }

    /**
     * 交换位置
     *
     * @param arr
     * @param source
     * @param target
     */
    static void swap(int[] arr, int source, int target) {
        int temp = arr[target];
        arr[target] = arr[source];
        arr[source] = temp;
    }

    /**
     * 打印数组
     *
     * @param arr
     */
    static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}
